class TreeNode:
    def __init__(self, x, left = None, right = None):
        self.val = x
        self.left = left
        self.right = right


class Solution:
    def target_path(self, root, target):

        res = []
        def dfs(root, path=None):
            if not root:
                return

            if not path:
                path = []
            path.append(root.val)

            if root.val == target:
                return res.append(list(path))
            else:
                dfs(root.left, path)            
                dfs(root.right, path)            
                path.pop()
        
        dfs(root)
        return res
if __name__ == '__main__':
    s = Solution()
    root = TreeNode(3, 
                TreeNode(5,
                    TreeNode(6),
                    TreeNode(2,
                        TreeNode(7),
                        TreeNode(4))),
                TreeNode(1, 
                    TreeNode(0),
                    TreeNode(8)))
    
    path = s.target_path(root, 7)
    print(path)
    path = s.target_path(root, 4)
    print(path)


            
